let _ = [1; 2; 3; 4; 5]
let _ = 1::2::3::4::5::[]
let _ = [1; 2] @ [3; 4; 5]

let rec product = function
  | [] -> 1
  | h::t -> h * product t

let rec foldr f acc = function
  | [] -> acc
  | h::t -> f h (foldr f acc t)

let concat strs = List.fold_right (^) strs ""
let _ = concat ["hello"; "world"; "fuck"]

let first_is_abc = function
  | "abc"::xxx -> true
  | _ -> false;;

assert (first_is_abc ("abc"::[]));;
assert (not (first_is_abc ("abd"::[])));;

let list_len_is_four_or_two = function
  | [_; _] | [_; _; _; _] -> true
  | _ -> false;;

assert (list_len_is_four_or_two [1; 2]);;
assert ([1; 2; 3] |> list_len_is_four_or_two |> not);;

let list_first_and_second_eq = function
  | a::b::t when a = b -> true
  | _ -> false;;

let return_list_5th_or_zero lst =
  if List.length lst > 5
  then (List.nth lst 4)
  else 0

let sort_int_list lst =
  List.sort Int.compare lst
  |> List.rev;;

sort_int_list [1; 3; 2; 0];; (* [3; 2; 1; 0] *)

let list_last lst = List.length lst |> (-) 1 |> List.nth lst;;
let any_zeros lst = List.fold_right (fun a b -> b || (a = 0)) lst false;;

assert (any_zeros [1; 2; 0]);;
assert (any_zeros [1; 2; 3] |> not);;

let take lst n =
  let rec inner = function
    | h::t, num, acc -> inner (t, (num - 1), h::acc)
    | _, 0, acc -> acc
    | [], _, acc -> acc
  in inner (lst, n, [])


type sex = Man | Woman
type student = {name: string; age: int; sex: sex}

let safe_hd = function
  | [] -> None
  | h::t -> Some h

type date = {year: int; month: int; day: int}

let is_before b a =
  a.year > b.year ||
    a.month > b.month ||
      a.day > b.day

let list_min compare lst =
  let rec inner cur_min = function
    | [] -> cur_min
    | h::t -> if compare h cur_min then inner cur_min t else inner h t
  in inner (List.hd lst) (List.tl lst)

type 'a tree = Leaf | Node of 'a tree_node
and
'a tree_node = {left: 'a tree; value: 'a; right: 'a tree}

let rec is_bst = function
  | {left = Node l; value; right = Node r} ->
     if l.value < r.value
     then is_bst l && is_bst r
     else false
  | {left = Leaf; value; right = Node r} -> is_bst r
  | {left = Node l; value; right = Leaf} -> is_bst l
  | {left = Leaf; value; right = Leaf} -> true

let is_bst' = function
  | Leaf -> true
  | Node n -> is_bst n

let sign n =
  if n > 0 then `Pos
  else if n = 0 then `Zero
  else `Neg
